package Leetcode.每日一题;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @ClassName 满足不等式的最大值
 * @since: 2023/7/21 22:43
 * @auth: kirito
 * @description:
 * 自己思路：在j-i《=k 情况下求 yi + yj + |xi - xj| 的 最大值
 * 公共子序列？  但是这个应该不能一维数组解决  得n*n
 * 然后每i行第j列 存k为i的最大值
 * 0行都0
 * 1行即相邻和
 * 2行间隔1个的和
 * 回顾一下公共子序列：动态规划 最大数组和 多数之和--
 **/
public class 满足不等式的最大值 {
    public static int findMaxValueOfEquation(int[][] points, int k) {
        int res = Integer.MIN_VALUE;
        Deque<int[]> queue = new ArrayDeque<int[]>();
        for (int[] point : points) {
            int x = point[0], y = point[1];
            while (!queue.isEmpty() && x - queue.peekFirst()[1] > k) {
                queue.pollFirst();
            }
            if (!queue.isEmpty()) {
                res = Math.max(res, x + y + queue.peekFirst()[0]);
            }
            while (!queue.isEmpty() && y - x >= queue.peekLast()[0]) {
                queue.pollLast();
            }
            queue.offer(new int[]{y - x, x});
        }
        return res;

    }
}